package com.atguigu.algorithm;

public class RabinKarp2 {
    final static long seed=31;

    public static void main(String[] args) {
        String s="ABABABA";
        String p="ABA";
        long[] hash=hash(s,p.length());
        long hash1=hash(p);
        for(int i=0;i<hash.length;i++){
            if(hash[i]==hash1){
                System.out.println("match:"+i);
            }
        }
    }
    static long hash(String str){
        long hash=0;
        for(int i=0;i<str.length();i++){
            hash=seed*hash+str.charAt(i);
        }
        return hash;
    }
    static long[] hash(String s,int M){
        //利用滚动方法，求取一个hash数组
        long[] res=new long[s.length()-M+1];
        //前m个字符的hash
        res[0]=hash(s.substring(0,M)); //M其实就是短数组的长度
        for(int i=M;i<s.length();i++){
            char newChar=s.charAt(i);
            char oldChar=s.charAt(i-M);
            long v=(res[i-M]*seed+newChar-(long)Math.pow(seed,M)*oldChar)%Long.MAX_VALUE;
            res[i-M+1]=v;
        }
        return res;
    }
}
